package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  快速排序
 *
 *    时间复杂度  O(n^2)
 *    稳定性     不稳定
 */
public class FastSort {

    public static void main(String[] args) {

        int[] arr = {2,35,65,123,6,7,12,1};

        System.out.println(Arrays.toString(arr));

        sort(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));

    }

    public static int[] sort(int[] arr, int left, int right){

        if(arr.length < 1 || left > right){
            return arr;
        }

        int partitionIndex = partition(arr, left, right);
//        int partitionIndex = partitionTwoWay(arr, left, right);

        sort(arr, left, partitionIndex - 1);

        sort(arr, partitionIndex + 1, right);

        return arr;
    }

    public static int partition(int[] arr, int left, int right){
        // 基准索引
        int pivot = (int) (left + Math.random() * (right - left + 1));
        // 分区指示器
        int partitionIndex = left - 1;
        //  交换基准和尾
        swap(arr, pivot, right);
        // 开始排序
        for (int i = left; i <= right; i++) {
            // 如果当前元素比基准小的话 分区指示器向右移动一个元素
            if(arr[i] <= arr[right]){
                partitionIndex ++;
                // 当前索引大于分区指示器 交换两个元素
                if(i > partitionIndex){
                    swap(arr, i, partitionIndex);
                }
            }
        }
        return partitionIndex;
    }

    /**
     *  双向扫描
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partitionTwoWay(int[] array, int left, int right) {
        //基准数
        int pivot = array[right];
        //左分区指示器索引
        int leftIndex = left - 1;
        //右分区指示器索引
        int rightIndex = right;
        //索引
        int index = left;
        while (index < rightIndex) {
            //若当前元素大于基准数，右分区指示器左移一位，当前元素和右分区指示器所指元素交换，索引保持不变
            if (array[index] > pivot) {
                swap(array, index, --rightIndex);
            } else if (array[index] <= pivot) {//当前元素小于等于基准数时，左分割指示器右移一位，索引右移
                leftIndex++;
                index++;
                //当前元素小于等于左分区指示器所指元素，交换
                if (array[index] < array[leftIndex]) {
                    swap(array, index, leftIndex);
                }
            }
        }
        //索引和 L 指向同一个元素
        swap(array, right, rightIndex);
        return 1;
    }

    public static void swap(int[] arr, int x, int y){
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

}
